//
// Created by Snow on 2023/3/14.
//
#include<cstdio>
#include<cstdlib>
#define MaxSize 50
#define M 8
#define N 8
int mg[M+2][N+2]={{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},
                  {1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},
                  {1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},
                  {1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},
                  {1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}};
typedef struct
{
    int i,j;//方块的位置
    int pre;//本路径中上一个方块在队列中的下标
}Box;//方块类型
typedef struct
{
    Box data[MaxSize];
    int front,rear;//队头指针和队尾指针
}QuType;
void InitQueue(QuType *&qu)
{
    qu=(QuType *)malloc(sizeof(QuType));
    qu->front=qu->rear=-1;
}
void DestroyStack(QuType *&qu)
{
    free(qu);
}
bool QueueEmpty(QuType *qu)
{
    return(qu->front==qu->rear);
}
bool enQueue(QuType *&qu,Box e)
{
    if(qu->rear==MaxSize-1)
        return false;
    qu->rear=qu->rear+1;
    qu->data[qu->rear]=e;
    return true;
}
bool deQueue(QuType *&qu,Box &e)
{
    if(qu->front==qu->rear)
        return false;
    qu->front=qu->front+1;
    e=qu->data[qu->front];
    return true;
}
void print(QuType *qu,int front)
{
    int k=front,j,ns=0;
    printf("\n");
    do
    {
        j=k;
        k=qu->data[k].pre;
        qu->data[j].pre=-1;
    }while(k!=0);
    printf("the way is:\n");
    k=0;
    while(k<MaxSize)
    {
        if(qu->data[k].pre==-1)
        {
            ns++;
            printf("\t(%d,%d)",qu->data[k].i,qu->data[k].j);
            if(ns%5==0)printf("\n");
        }
        k++;
    }
    printf("\n");
}
bool mgpath1(int xi,int yi,int xe,int ye)
{
    Box e;
    int i,j,di,i1,j1;
    QuType *qu;
    InitQueue(qu);
    e.i=xi;
    e.j=yi;
    e.pre=-1;
    enQueue(qu,e);
    mg[xi][yi]=-1;
    while(!QueueEmpty(qu))
    {
        deQueue(qu,e);
        i=e.i;
        j=e.j;
        if(i==xe&&j==ye)
        {
            print(qu,qu->front);
            DestroyStack(qu);
            return true;
        }
        for(di=0;di<4;di++)
        {
            switch(di)
            {
                case 0:i1=i-1;j1=j;break;
                case 1:i1=i;j1=j+1;break;
                case 2:i1=i+1;j1=j;break;
                case 3:i1=i;j1=j-1;break;
            }
            if(mg[i1][j1]==0)
            {
                e.i=i1;
                e.j=j1;
                e.pre=qu->front;
                enQueue(qu,e);
                mg[i1][j1]=-1;
            }
        }
    }
    DestroyStack(qu);
    return false;
}
int main()
{
    if(!mgpath1(1,1,M,N))
        printf("fail\n");
    return 1;
}